{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4d09bbb8",
   "metadata": {},
   "source": [
    "## 1. 字符串压缩\n",
    "> **问题描述**： 给定一个段英文句子和一个英文单词列表， \n",
    "> 英文句子包含英文单词和标点符号，其中：\n",
    "> 1）英文单词只包含[a-zA-Z]范围内的字符；\n",
    "> 2）标点符号包含逗号，句号，双引号（双引号两边至少有一个空格）；\n",
    "> 如果列表中有单词在句子中存在（大小写不敏感）且该单词未被双引号包含，\n",
    "> 则使用该单词在列表中的索引值（索引值从0开始）代替句子中的该单词，\n",
    "> 如果英文单词列表中存在重复的英文单词，则以该单词的最好一次出现的额索引值进行替换\n",
    "\n",
    "\n",
    "> **解答要求**： 时间限制：C/C++ 400ms, 其他语言： 800ms； 内存限制：C/C++ 200MB, 其他语言： 400MB\n",
    "\n",
    "> **输入**： 第一行：一段英文句子；   第二行：英文单词列表；\n",
    "\n",
    "> **提示**： 每个英文单词长度在[1,50] 范围内； 输入的英文句子长度在[0,10000]范围内； 输入的英文单词的列表的长度在[0,100000]范围内；\n",
    "> 英文句子中不会出现双引号不匹配的情况.\n",
    "\n",
    "> **输出**: 替换后的英文句子\n",
    "    \n",
    "\n",
    "> **样例1**:\n",
    "    \n",
    "```\n",
    "输入: Hellow world.\n",
    "    Good Hello LOOP\n",
    "输出: 1 world.\n",
    "        \n",
    "解释: hello在英文句子中存在,使用hello的索引值进行替换,得到结果 1 world.\n",
    "```\n",
    "\n",
    "> **样例2**:\n",
    "    \n",
    "```\n",
    "输入: An introduction is \" the first paragraph \" of your paper.\n",
    "    what say first Second IS introduction IS end\n",
    "    \n",
    "输出: An 5 6 \" the first paragraph \" of your paper.\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c27ab63a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "An introduction is \" the first paragraph \" of your paper.\n"
     ]
    }
   ],
   "source": [
    "## 哈希表问题\n",
    "# 记录\"的位置状态\n",
    "_author_ = \"KongWeiren\"\n",
    "def q1(sent, dict_words_sent):\n",
    "    dict_words = list(map(lambda w: w.lower(), dict_words_sent))\n",
    "    \n",
    "    dictionary = {}\n",
    "    for i,keystr in enumerate(dict_words):\n",
    "        dictionary[keystr] = i\n",
    "    \n",
    "    dictionary_keys = set(dictionary.keys())\n",
    "    \n",
    "    result_words = []\n",
    "    words = sent.split()\n",
    "    quot = False\n",
    "    for word in words:\n",
    "        if word =='\"' and not quot:\n",
    "            quot = True\n",
    "            result_words.append(word)\n",
    "            continue\n",
    "        if word =='\"' and quot:\n",
    "            quot = False\n",
    "            result_words.append(word)\n",
    "            continue\n",
    "            \n",
    "        if not quot:\n",
    "            if word[-1]==\".\" or word[-1]=='.':\n",
    "                if word[:-1].lower() in dictionary_keys:\n",
    "                    result_words.append(str(dictionary[word[:-1].lower()])+word[-1])\n",
    "                else:\n",
    "                    result_words.append(word)\n",
    "            else:\n",
    "                if word.lower() in dictionary_keys:\n",
    "                    result_words.append(dictionary[word.lower()])\n",
    "                else:\n",
    "                    result_words.append(word)\n",
    "        else:\n",
    "            result_words.append(word)\n",
    "            \n",
    "    return ' '.join(result_words)\n",
    "\n",
    "def func():\n",
    "    sent = \"An introduction is \\\" the first paragraph \\\" of your paper.\" # input()\n",
    "    words = \"what say first Second IS introduction IS end\" # input()\n",
    "    print(q1(sent,words))\n",
    "    \n",
    "func()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "635013cb",
   "metadata": {},
   "source": [
    "### 2.  士兵的任务\n",
    "> 士兵在迷宫中执行任务,迷宫中危机重重,他需要在最短的时间里到达指定的位置,你可以告诉士兵他最少需要多长时间吗?\n",
    "> 输入一个 n*m 的迷宫, 迷宫中0为路, 1为墙, 2为起点， 3为终点， 4为陷阱，6为炸弹。 士兵只能上下左右四个方向移动， 如果路径上为墙，不能移动。\n",
    "\n",
    "> 已知每走一步需要花费1个单位的时间，走到陷阱上需要花费3个单位的时间，走到炸弹上面将会激活炸弹，炸弹引爆会把其上下左右的墙炸为路。\n",
    "\n",
    "> **注意**:\n",
    "> 1.炸弹只能炸毁墙,不能炸毁陷阱\n",
    "> 2.炸弹、陷阱只能发挥一次作用\n",
    "> 3.迷宫最大为 $25 \\times 25$\n",
    "> 4.用例保证士兵一定有办法到达终点\n",
    "\n",
    ">**解答要求**:\n",
    "> 时间限制: C/C++ 600ms, 其他语言: 12000ms; \n",
    "> 内存限制: C/C++ 256MB, 其他语言: 512MB;\n",
    "\n",
    "> **输入**:\n",
    "> 第一行: n m  \n",
    "> 第二行开始: $n \\times m$的矩阵\n",
    "\n",
    ">**输出**:\n",
    "> 最少需要的单位时间\n",
    "\n",
    ">**样例1**:\n",
    "\n",
    "```\n",
    "输入: 4 4\n",
    "    1 1 1 1\n",
    "    1 6 2 1\n",
    "    1 1 0 1\n",
    "    1 3 1 1\n",
    "输出: 3\n",
    "\n",
    "解释: 士兵在位置2,向左移动到炸弹上,引爆炸弹,向下走两步就到终点\n",
    "```\n",
    "\n",
    ">**样例2**\n",
    "\n",
    "```\n",
    "输入: 8 4\n",
    "    1 6 2 1\n",
    "    1 1 0 1\n",
    "    1 1 0 1\n",
    "    1 1 0 1\n",
    "    1 1 0 1\n",
    "    1 1 0 1\n",
    "    1 1 0 1\n",
    "    1 1 0 1\n",
    "    1 1 3 1\n",
    "输出: 7\n",
    "\n",
    "解释: 士兵在位置2, 向下移动7步即可到达终点\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "85674340",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a9e677ba",
   "metadata": {},
   "source": [
    "## 3. 高速公路休息站充电规划\n",
    "> **问题描述**: 一辆续航1000公里的电动汽车,从甲城到乙城,全程高速. 中间有N个休息站可以充电,各休息站可以实时提供当前充电排队时间(小时). 请规划时间最优的休息站充电方案,返回最短的旅行用时.\n",
    "\n",
    "> 车辆行驶速度固定为100KM/h,假设汽车可以把电用尽,1000公里续航的汽车,以100KM/h的速度可以形式10h; 每次充电时间固定为1小时, 完成后电量充满; 各个站点充电排队的时间不会变化,充电过程不耗电.\n",
    "\n",
    "> **解答要求**:\n",
    "> 时间限制: C/C++ 1000ms, 其他语言:2000ms; 内存限制: C/C++ 256MB, 其他语言: 512MB\n",
    "\n",
    "> **输入**:\n",
    "```\n",
    "第一行表示甲乙两城的距离D,单位为公里;\n",
    "第二行表示沿途的休息站数量 N\n",
    "第三行起, 每行两个数据,分别表示休息站距离甲城的距离,以及排队时间(小时),各个休息站按距离从近到远排序\n",
    "```\n",
    "$ 0 \\le D \\le 1000000$, D是100的整数倍; $0 \\le N \\le 10000$\n",
    "\n",
    "> **输出**\n",
    "```\n",
    "旅程总的花费时间(小时); 若无法到达返回 -1\n",
    "```\n",
    "\n",
    "> **样例 1**\n",
    "\n",
    "```\n",
    "输入: 1500\n",
    "    4\n",
    "    300 2\n",
    "    600 1\n",
    "    1000 0\n",
    "    1200 0\n",
    "输出: 16\n",
    "\n",
    "解释: 最佳方案: 只在第三个休息站(位置1000)进行充电,\n",
    "1500公里,耗时 15h\n",
    "排队充电时间: 0h\n",
    "充电时间: 1h\n",
    "```\n",
    "\n",
    "> **样例 2**\n",
    "```\n",
    "输入: 800\n",
    "    2\n",
    "    300 0\n",
    "    600 0\n",
    "输出: 8\n",
    "\n",
    "解释: 不充电\n",
    "```\n",
    "> **样例 3**\n",
    "\n",
    "```\n",
    "输入: 2000\n",
    "    4\n",
    "    300 2\n",
    "    600 0\n",
    "    900 0\n",
    "    1950 3\n",
    "输出: -1\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "188aab10",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
